package demo1;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:咭咭熊
 * Date:2021 - 08 - 10
 * Time:19:20
 */

import java.util.ArrayList;
import java.util.LinkedList;

/****
 * 输入一棵二叉树，求该二叉树的深度；
 * 从根节点到叶节点依次经过的节点形成数的一条路径，最长类路径的长度为树的深度
 * 输入：{1,2,3,4,5,#,6,#,#,7}
 * 返回值：4
 */
class TreeNode{
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val){
        this.val = val;
    }
}
public class Test8 {

    /***
     * 方法1：递归实现
     * 如果该树只有一个节点，其深度为1；
     * 如果该树只有左子树没有右子树，那么树的深度为左子树的深度 + 1；
     * 如果该树只有右子树没有左子树，那么树的深度为右子树的深度+ 1；
     * 如果既有左子树也有右子树，那么该树的深度就是左子树和右子树的最大值+ 1；
     * @param root
     * @return
     */
    public int TreeDepth1(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = TreeDepth1(root.left);
        int right = TreeDepth1(root.right);
        return Math.max(left,right) + 1;
    }


    //方法1：层次遍历——非递归实现——使用队列进行实现
    public ArrayList<ArrayList<Integer>> TreeDepth2(TreeNode root){
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> al = null;
        LinkedList<TreeNode> queue = new LinkedList<>();
        if( root == null ) return res;
        queue.add(root);
        while( !queue.isEmpty()){
            al = new ArrayList<>();
            int size = queue.size();
            for(int i=0;i<size;i++){
                TreeNode node = queue.removeFirst();
                al.add(node.val);
                if( node.left != null ){
                    queue.add(node.left);
                }
                if( node.right != null ){
                    queue.add(node.right);
                }
            }
            res.add(al);
        }
        return res;
    }
}
